COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	prolog.not[w82,jmc]	Notes on control in logic programming
C00004 ENDMK
C⊗;
prolog.not[w82,jmc]	Notes on control in logic programming

Predicate Logic as a Computational Formalism, Keith L. Clark

Problem: develop a program that can solve the eight queens problem
without knowing in advance that there can be only one queen in
each row and column.  It should deduce this fact and only then
choose an appropriate representation for the heuristic search.
Only this would be an honest solution of the eight queens problem.

← Queen_sol(1.2. ... .8.nil,y)

	Queen_sol(x,y) ← Perm(x,y) & Safe(y)

We have

	Perm(Nil,Nil) ←

	Perm(u.x, v.z) ← delete(v, u.x, y) ∧ Perm(y, z)

where

	delete(u, u.x, x) ←

	delete(u, v.x, v.z) ← delete(u, x, z).

The  Safe  relation is given by

	Safe(Nil) ←

	Safe(u.x) ← no_take(u, x, 1) ∧ Safe(x)

where

	no_take(u, Nil, n) ←

	no_take(u, v.x, n) ← no_diagonal(u, v, n) ∧ no_take(u, x, s(n))

and

	no_diagonal(u, v, n) ← v > u ∧ v = u+w ∧ w ≠ n

	no_diagonal(u, v, n) ←  u > v  ∧ u = v+w ∧ w ≠ n